package _go

func maxSubArray(nums []int) int {

	dp := make([]int, len(nums))
	//dp定义  到第i个为止的最大和
	dp[0] = nums[0] //初始化是第一个数
	res := nums[0]
	for i := 1; i < len(nums); i++ {

		//第i位的最大和是i-1d最大和加上当前位 和当前为比较  谁大
		//因为有可能是负值  还不如当前值自己大
		dp[i] = max(dp[i-1]+nums[i], nums[i])
		//dp = tmp
		if dp[i] > res {
			res = dp[i]
		}
	}
	return res
}

//空间优化
func maxSubArray2(nums []int) int {
	res := nums[0]
	dp := nums[0]
	for i := 1; i < len(nums); i++ {
		//结果只跟前一个dp有关 只需要一个dp就够了
		dp = max(dp+nums[i], nums[i])
		if dp > res {
			res = dp
		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}
